Decode ways

Time: O(N); Space: O(1); medium

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: s = “12”

Output: 2

Explanation:

  • It could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = “226”

Output: 3

Explanation:

It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0 or s[0] == '0':
            return 0

        prev, prev_prev = 1, 0

        for i in range(len(s)):
            cur = 0
            if s[i] != '0':
                cur = prev

            if i > 0 and (s[i - 1] == '1' or (s[i - 1] == '2' and s[i] <= '6')):
                cur += prev_prev

            prev, prev_prev = cur, prev

        return prev

[4]:

sol = Solution1()

s = "12"
assert sol.numDecodings(s) == 2

s = "226"
assert sol.numDecodings(s) == 3